package problem241_Different_Ways_to_Add_Parentheses;

import java.util.LinkedList;
import java.util.List;

public class Solution {
	public List<Integer> diffWaysToCompute(String input) {
		List<Integer> result=new LinkedList<>();
		char[] chars=input.toCharArray();
		for(int i=0;i<chars.length;i++){
			if(Character.isDigit(chars[i]))continue;
			List<Integer> left=diffWaysToCompute(input.substring(0,i));
			List<Integer> right=diffWaysToCompute(input.substring(i+1));
			for(int l:left){
				for(int r:right){
					switch(chars[i]){
					case '+':
						result.add(l+r);
						break;
					case '-':
						result.add(l-r);
						break;
					case '*':
						result.add(l*r);
						break;
					}
				}
			}
		}
		if(result.isEmpty())
			result.add(Integer.parseInt(input));
		return result;
	}
}
